package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 437. 路径总和 III
 * 前缀和
 *
 * @author fy
 * @date 2022/4/25 17:47
 */
public class Solution437_3 {

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        // 前缀和为0的路径个数有1个（满足单节点路径的合法性）
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret;
        curr += root.val;

        // 这里一定要先计算以当前节点为结尾满足和为target的路径条数，再将当前节点加入哈希表，即要保证路径不能为空
        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        // 递归至当前节点左右子树
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        // 当前节点计算结束，回溯删除当前节点
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }

}
